package alogrithm;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/10/16 10:01
 */
public class Merge {

    public static void main(String[] args) {
        new Merge().merge(new int[]{4, 5, 6}, 3, new int[]{1, 2, 3}, 3);
    }
    public void merge(int[] A, int m, int[] B, int n) {

        for (int i = 0; i < n; ++i) {
            A[m + i] = B[i];
        }
        sort(A, 0, m + n);
    }

    private void sort(int[] a, int l, int r) {
        if (l < r) {
            int mid = (l + r) / 2;
            sort(a, l, mid);
            sort(a, mid + 1, r);
            mergeSort(a, l, mid, r);
        }

    }

    private void mergeSort(int[] a, int l, int mid, int r) {
        int i = l, j = mid + 1;
        int[] b = new int[a.length];
        for (int k = l; k < r; ++k) {
            b[k] = a[k];
        }
        int k = l;
        while (i < mid || j < r) {
            if (i > mid) a[k++] = b[j];
            if (j > r) a[k++] = b[i];
            if (a[j] <= a[i]) a[k++] = b[j];
            if (a[i] < a[j]) a[k++] = b[i];
        }
    }
}
